home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_09_02 / 9n02058a < prev    next >
Text File  |  1990-12-22  |  25KB  |  595 lines
  1.  
  2. /***********************************************************
  3.  *  Node-Positioning for General Trees, by John Q. Walker II
  4.  *
  5.  *  Initiated by calling procedure TreePosition().
  6.  **********************************************************/
  7.  
  8. #include <stdlib.h>
  9.  
  10. /*----------------------------------------------------------
  11.  * Implementation dependent: Set the values for each of
  12.  * these variables.
  13.  *--------------------------------------------------------*/
  14. #define NODE_WIDTH          20  /* Width of a node?       */
  15. #define NODE_HEIGHT         10  /* Height of a node?      */
  16. #define FRAME_THICKNESS     1   /* Fixed-sized node frame?*/
  17. #define SUBTREE_SEPARATION  5   /* Gap between subtrees?  */
  18. #define SIBLING_SEPARATION  4   /* Gap between siblings?  */
  19. #define LEVEL_SEPARATION    5   /* Gap between levels?    */
  20. #define MAXIMUM_DEPTH       10  /* Biggest tree?          */
  21.  
  22. /*----------------------------------------------------------
  23.  * Implementation dependent: The structure for one node
  24.  * - The first 4 pointers must be set for each node before
  25.  *   this algorithm is called.
  26.  * - The X and Y coordinates must be set for only the apex
  27.  *   of the tree upon entry; they will be set by this
  28.  *   algorithm for all the other nodes.
  29.  * - The next three elements are used only for the duration
  30.  *   of the algorithm.
  31.  * - Actual contents of the node depend on your application.
  32.  *--------------------------------------------------------*/
  33. typedef int COORD;              /* X,Y coordinate type    */
  34.  
  35. typedef struct node {
  36.     struct node *parent;        /* ptr: node's parent     */
  37.     struct node *offspring;     /* ptr: leftmost child    */
  38.     struct node *leftsibling;   /* ptr: sibling on left   */
  39.     struct node *rightsibling;  /* ptr: sibling on right  */
  40.     COORD  xCoordinate;         /* node's current x coord */
  41.     COORD  yCoordinate;         /* node's current y coord */
  42.  
  43.     struct node *prev;          /* ptr: lefthand neighbor */
  44.     float  flPrelim;            /* preliminary x coord    */
  45.     float  flModifier;          /* temporary modifier     */
  46.  
  47.     char   info[80];            /* pick your contents!    */
  48. } *PNODE;                       /* ptr: a node structure  */
  49.  
  50. /*----------------------------------------------------------
  51.  * Global variables used by the algorithm
  52.  *--------------------------------------------------------*/
  53. typedef enum { FALSE, TRUE } BOOL;
  54. typedef enum { FRAME, NO_FRAME } FRAME_TYPE;
  55. typedef enum { NORTH, SOUTH, EAST, WEST } ROOT_ORIENTATION;
  56.  
  57. typedef struct prev_node {      /* one list element       */
  58.     PNODE pPreviousNode;        /* ptr: previous at level */
  59.     struct prev_node *pNextLevel;   /* ptr: next element  */
  60. } *PPREVIOUS_NODE;
  61.  
  62. static FRAME_TYPE FrameType = FRAME;    /* Show a frame   */
  63. static ROOT_ORIENTATION RootOrientation = NORTH; /* At top*/
  64. static PPREVIOUS_NODE pLevelZero = (PPREVIOUS_NODE)0;
  65.  
  66. static COORD xTopAdjustment;    /* How to adjust the apex */
  67. static COORD yTopAdjustment;    /* How to adjust the apex */
  68. static float flMeanWidth;       /* Ave. width of 2 nodes  */
  69.  
  70. #define FIRST_TIME  (0)         /* recursive proc flag    */
  71.  
  72. /*----------------------------------------------------------
  73.  * Implemented as macros, but could be implemented as
  74.  * procedures depending on your particular node structures
  75.  *--------------------------------------------------------*/
  76. #define FirstChild(node)     ((PNODE)((node)->offspring))
  77. #define LeftSibling(node)    ((PNODE)((node)->leftsibling))
  78. #define RightSibling(node)   ((PNODE)((node)->rightsibling))
  79. #define Parent(node)         ((PNODE)((node)->parent))
  80. #define LeftNeighbor(node)   ((PNODE)((node)->prev))
  81. #define IsLeaf(node)          \
  82.                (((node)&&(!((node)->offspring)))?TRUE:FALSE)
  83. #define HasChild(node)        \
  84.                   (((node)&&((node)->offspring))?TRUE:FALSE)
  85. #define HasLeftSibling(node)  \
  86.                 (((node)&&((node)->leftsibling))?TRUE:FALSE)
  87. #define HasRightSibling(node) \
  88.                (((node)&&((node)->rightsibling))?TRUE:FALSE)
  89.  
  90.  
  91. static PNODE GetPrevNodeAtLevel (unsigned nLevelNbr)
  92. {
  93.     /*------------------------------------------------------
  94.      * List Manipulation: Return pointer to previous node at
  95.      * this level
  96.      *----------------------------------------------------*/
  97.     PPREVIOUS_NODE pTempNode;   /* used in the for-loop   */
  98.     unsigned  i = 0;            /* level counter          */
  99.  
  100.     for (pTempNode = pLevelZero; (pTempNode);
  101.          pTempNode = pTempNode->pNextLevel) {
  102.         if (i++ == nLevelNbr)
  103.             /* Reached desired level.  Return its pointer */
  104.             return (pTempNode->pPreviousNode);
  105.     }
  106.     return ((PNODE)0);  /* No pointer yet for this level. */
  107. }
  108.  
  109. static BOOL SetPrevNodeAtLevel (unsigned nLevelNbr,
  110.                                 PNODE pThisNode)
  111. {
  112.     /*------------------------------------------------------
  113.      * List Manipulation: Set the list element to the
  114.      * previous node at this level
  115.      *----------------------------------------------------*/
  116.  
  117.     PPREVIOUS_NODE pTempNode;   /* used in the for-loop   */
  118.     PPREVIOUS_NODE pNewNode;    /* newly-allocated memory */
  119.     unsigned  i = 0;            /* level counter          */
  120.  
  121.     for (pTempNode = pLevelZero; (pTempNode);
  122.          pTempNode = pTempNode->pNextLevel) {
  123.         if (i++ == nLevelNbr) {
  124.             /* Reached desired level.  Return its pointer */
  125.             pTempNode->pPreviousNode = pThisNode;
  126.             return (TRUE);
  127.         }
  128.         else if (pTempNode->pNextLevel==(PPREVIOUS_NODE)0) {
  129.             /* Looks like we need a new level: add it.    */
  130.             /* We need to keep going--should be the next. */
  131.             pNewNode = (PPREVIOUS_NODE)
  132.                        malloc(sizeof(struct prev_node));
  133.             if (pNewNode) {
  134.                 pNewNode->pPreviousNode = (PNODE)0;
  135.                 pNewNode->pNextLevel = (PPREVIOUS_NODE)0;
  136.                 pTempNode->pNextLevel = pNewNode;
  137.             }
  138.             else return (FALSE);    /* The malloc failed. */
  139.         }
  140.     }
  141.  
  142.     /* Should only get here if pLevelZero is 0.           */
  143.     pLevelZero = (PPREVIOUS_NODE)
  144.                  malloc(sizeof(struct prev_node));
  145.     if (pLevelZero) {
  146.         pLevelZero->pPreviousNode = pThisNode;
  147.         pLevelZero->pNextLevel = (PPREVIOUS_NODE)0;
  148.         return (TRUE);
  149.     }
  150.     else return (FALSE);        /* The malloc() failed.   */
  151. }
  152.  
  153. static void InitPrevNodeAtLevel (void)
  154. {
  155.     /*------------------------------------------------------
  156.      * List Manipulation: Initialize the list of the
  157.      * previous node at each level to all zeros.
  158.      *----------------------------------------------------*/
  159.  
  160.     PPREVIOUS_NODE pTempNode = pLevelZero;  /* the start  */
  161.  
  162.     for ( ; (pTempNode); pTempNode = pTempNode->pNextLevel)
  163.         pTempNode->pPreviousNode = (PNODE)0;
  164. }
  165.  
  166. static BOOL CheckExtentsRange(long lxTemp, long lyTemp)
  167. {
  168.     /*------------------------------------------------------
  169.      * Insert your own code here, to check when the
  170.      * tree drawing is going to be too big.  My region is no
  171.      * more that 64000 units square.
  172.      *----------------------------------------------------*/
  173.  
  174.     if ((labs(lxTemp) > 32000) || (labs(lyTemp) > 32000))
  175.         return (FALSE);
  176.     else
  177.         return (TRUE);
  178. }
  179.  
  180. static void TreeMeanNodeSize (PNODE pLeftNode,
  181.                               PNODE pRightNode)
  182. {
  183.     /*------------------------------------------------------
  184.      * Write your own code for this procedure if your
  185.      * rendered nodes will have variable sizes.
  186.      *------------------------------------------------------
  187.      * Here I add the width of the contents of the
  188.      * right half of the pLeftNode to the left half of the
  189.      * right node.  Since the size of the contents for all
  190.      * nodes is currently the same, this module computes the
  191.      * following trivial computation.
  192.      *----------------------------------------------------*/
  193.  
  194.     flMeanWidth = (float)0.0;   /* Initialize this global